import java.util.ArrayList;
import java.util.List;

/**
 * This is a version of the classic puzzle with a number of pieces, that can
 * only be moved by changing the position of the one empty field. In this game,
 * one has to predict the moves to be made, to solve the puzzle, and via the GUI
 * make a route for the empty field to follow (until it is in the leftmost lower
 * corner). This tests the players ability to remember, think forward and gives
 * you a lot of possible score-strategies. E.g. how fast can one solve the puzzle,
 * how few routes could one use to solve the puzzle, etc. Some of these will be
 * implemented in the final edition. 
 * @author Dr. Quul
 */
public class PuzzleGame implements Game {

	private int GAMESIZE;
	protected String[] direction = {"left", "up", "right", "down"};
	private MapView map;
	private List<GameListener> listeners;
	private int steps = 0;

	public PuzzleGame(int gamesize) {
		GAMESIZE = gamesize;
		map = new MapView(new Field[GAMESIZE][GAMESIZE]);
		setupMap();
		listeners = new ArrayList<GameListener>();
		textMap();
	}
	
	/**
	 * Determines whether the fields at position from and position to is next to each other
	 * @param from
	 * @param to
	 * @return true if the fields are next to each other and false, else.
	 */
	public boolean isNextTo(Position from, Position to) {
		return map.isNextTo(from, to);
	}
	
	/**
	 * Sets up the map. E.g if GAMESIZE = 3, the map will look like:
	 * 1 2 3
	 * 4 5 6
	 * 7 8 e
	 * Where e is the empty field
	 */
	public void setupMap() {
		map.setupMap();
	}
	
	/**
	 * Scrambles the map by moving the empty field the value of difficulty times.
	 * Note that this is by no means the most correct algorithm for scrambling the map.
	 * E.g. by calling scramble(16) we could wind up in the situation where the map hasn't
	 * been changed at all. The probability of this, however is 4^-16. It is, however
	 * probably the easiest algorithm. I believe the problem is solved (not completely, and 
	 * I am not 100% sure about this) by, from user-input, calculating some sort of internal-
	 * difficulty value with the use of prime numbers, powers, etc.
	 * @param difficulty the allowed moves to scramble the map.
	 */
	public void scramble(int difficulty) {
		map.scramble(difficulty);
	}
	
	/**
	 * This probably should catch an IndexOutOfBoundsException,
	 * but since the method is private, I am sure it will only
	 * be called internally, where I myself will take care that
	 * it only will be called with the correct parameters.
	 * @param position the position to return the field at
	 * @return the field at the Position position
	 */
	public Field getFieldAt(Position pos) {
		return map.getFieldAt(pos);
	}
	
	public Field getFieldAt(int x, int y) {
		return map.getFieldAt(x, y);
	}
	
	public Position getPosition(int x, int y) {
		return map.getPosition(x, y);
	}
	
	public Position getNullPos() {
		return map.getNullPos();
	}

	/**
	 * @param nullPos the position of the empty field
	 * @param direction the direction the empty field should be moved
	 * @return true if the empty field was moved and false, else.
	 */
	public boolean canMove(Position nullPos, String direction) {
		return map.canMove(nullPos, direction);
	}
	
	/**
	 * Moves the empty field
	 * @param nullPos the position of the (empty) field
	 * @param direction the direction to move the (empty) field at position nullPos
	 */
	public void move(Position nullPos, String direction) {
		map.move(nullPos, direction);
	}
	
	public void move(Position nullPos, Position to) {
		map.move(nullPos, to);
		steps++;
		changed();
	}
	
	private void changed() {
		textMap();
		GameEvent e = new GameEvent(isSolved(), steps);
		for(GameListener l : listeners) {
			l.gameChanged(e);
		}
	}

	/**
	 * @return the specified GAMESIZE;
	 */
	public int getGamesize() {
		return GAMESIZE;
	}
	
	/**
	 * Calculates the least needed moves to solve the puzzle.
	 * This will be used by (some of) the score strategies.
	 * @return the least needed moves to solve the puzzle.
	 */
	@SuppressWarnings("unchecked")
	public int leastNeededMoves() {
		/**
		 * The overall algorithm is figured out - left to do is
		 * implementing it. The algorithm runs in O(3^n) time,
		 * where n is the least needed moves.
		 * The algorithm is essentially correct, but the time-
		 * complexity is way over the top. But until I have time
		 * to figure out how to use the A*-algorithm, this will
		 * have to do.
		 */
		//Setup the tree with the current map as root element
		Tree<MapView> tree = new Tree<MapView>();
		Node<MapView> rootElement = new Node<MapView>(new MapView(map.getMap()));
		tree.setRootElement(rootElement);
		//Make to lists of Nodes: one with the ones to be walked, and
		//one with their children. The first to be walked is the root element
		List<Node<MapView>> toBeWalked = new ArrayList<Node<MapView>>();
		List<Node<MapView>> children = new ArrayList<Node<MapView>>();
		toBeWalked.add(tree.getRootElement());
		//Instantiate the goal state
		MapView solvedMapView = new MapView(new Field[GAMESIZE][GAMESIZE]);
		solvedMapView.setupMap();
		Node<MapView> solvedNode = new Node<MapView>(solvedMapView);
		//The algorithm that adds Nodes to the tree, until it
		//contains the goal state (solvedNode).
		while(!toBeWalked.contains(solvedNode)) {
			for(Node<MapView> node : toBeWalked) {
				//For every node to be walked, get the position of the null
				//element. Give it as an argument to
				Position nullPos = node.getData().getNullPos();
				for(int i = 0; i < 4; i++) {
					Node<MapView> tmp = (Node<MapView>) node.clone();
					MapView tmpMap= tmp.getData();
					tmpMap.move(nullPos, direction[i]);
					if(!node.equals(tmpMap)) {
						node.addChild(tmp);
					}
				}
				children.addAll(node.getChildren());
			}
			toBeWalked.clear();
			toBeWalked.addAll(children);
			children.clear();
		}
		Node<MapView> goal = null;
		for(Node<MapView> node : toBeWalked) {
			if(node.equals(solvedNode)) {
				goal = node;
			}
		}
		return tree.depth(goal);
	}
	
	public boolean isSolved() {
		return map.isSolved();
	}
	
	public void addGameListener(GameListener listener) {
		listeners.add(listener);
	}
	
	private void textMap() {
		String s = "";
		for(int i = 1; i <= GAMESIZE; i++) {
			for(int j = 1; j <= GAMESIZE; j++) {
				s += getFieldAt(new Position(j,i)) + " ";
			}
			System.out.println(s);
			s = "";
		}
	}
}
